The disclosed invention relates in general to the management of memory in a computer system having a number of independent programming environments, each of which consists of a varying number of dynamic structures. More particularly, the disclosed invention relates to a technique which minimizes or at least reduces interference between independent programming environments.
A problem which is apparent in the computer art is a need to efficiently manage computer resources so that the computer capabilities are fully utilized and realized. As memory size, computer speed and computing power have increased, it has become apparent that new generations of single user computers are becoming capable of handling a number of tasks concurrently. The single user can benefit from the flexibility of dedicating his computer to a single task or concurrently executing many tasks. It is therefore advantageous to develop a storage management technique which enables several tasks to be active at the same time without interfering with one another. Of particular interest in a single user computer is the ability to enter, edit and debug a program while other programs are being executed.
This multiplicity of active tasks increases the multiplicity of dynamic structures in the computer's storage further increasing the need to efficiently manage such structures. A storage management technique is therefore needed which reduces or minimizes unintentional interaction of independent tasks such as the movement of one task in memory in order to make memory available for another task.
In general, there are a wide variety of dynamic structures utilized in even a single user, single task machine. Programs entered into the computer are stored in memory, both in their original form as text and in machine executable form. Data structures of various kinds are stored in memory. Special data structures called stacks, into which data are stored and accessed in a Last In First Out Manner, are frequently used for temporary data storage and management of program control flow involving nested functions and subroutines. All of the above mentioned objects are dynamic structures in the sense that they require allocation, extension, and deallocation of memory over time.
To most efficiently utilize available memory, it is advantageous to dynamically allocate a variable amount of memory to these dynamic structures only as needed rather than to allocate each a fixed amount of memory. A fixed allocation results in much of such allocated memory being unused in most applications and also puts inflexible upper limits on the memory allocated to each of the structures. As discussed, beginning at page 77, in the text by P. J. Brown entitled "Writing Interactive Compilers and Interpreters", John Wiley and Sons, 1979, the use of more than one dynamic structure requires storage management strategies to avoid writing over the information in one dynamic structure with information in another dynamic structure. Typically, dynamic structures have one fixed edge and one movable edge at which information is added or removed. Memory management can be simplified somewhat by placing pairs of dynamic structures in memory back to back as in FIGS. 1A-1C so that the dynamic edges of paired structures expand away from each other. When two dynamic edges meet (such as the dynamic edges of structures 2 and 3 in FIG. 1B), then one or more of the dynamic structures must be moved to make memory available for these two dynamic structures. In FIG. 1C is shown an example in which dynamic structures 1 and 2 were moved up and dynamic structures 3 and 4 were moved down to make available unused memory for dynamic structures 2 and 3. This scheme enables maximum use of memory at the expense of time consuming movement of one or more blocks of memory. It also prevents the use of absolute pointers--all pointers must be relative to the fixed edge of its associated dynamic structure so that when its associated fixed edge is moved in a block move of memory, all pointers will remain valid. In any case, the space in which the dynamic structures have available to expand is limited by the two boundaries forming the upper and lower extremes of the address space.
In another common storage management technique, dynamic structures are not necessarily generated in a contiguous segment of memory, but instead when more storage is required a master routine takes a controllable amount of memory from a common pool and makes it available to the dynamic structure needing more memory. The various blocks of memory made available to a given dynamic structure are not necessarily contiguous, but instead are linked together by a linked list which enables a jump from the end of one block to the beginning of the next block. In some systems, as sections of memory become unused, they are automatically returned to the common pool. This approach has the disadvantage that lists use up some of the memory because of the pointer fields required for its implementation. This approach also can result in a program being stored in numerous small fragments thereby requiring numerous jumps during execution. For example, if an N.times.N matrix is entered and overlaps onto several of these fragments, then a standard matrix operation such as matrix multiplication or inversion can require many jumps during execution. Thus, the management of linked lists is complicated and subject to errors.
In another storage management technique, memory is divided into pages of equal length. As discussed beginning at page 77 of the text by Lance A. Leventhal entitled "Introduction to Microprocessors: Software, Hardware and Programming" published by Prentice Hall, Inc. in 1978, a primary motive for using paged memory is that the length of the address portion of an instruction in a direct addressing scheme can be reduced. In a paged address approach, the address of a memory location is indicated by a page number and a line number within the page. In accessing a given address in memory, its page number is loaded into a page register and then the line number within that page is indicated by the direct address instruction. Because the length of the number needed to indicate the line number within a page is typically smaller than the length of a number needed to indicate a given memory address, this technique reduces the length of the address portion of an instruction.
In the same manner as the linked list approach, pages of memory can be allocated to a given dynamic structure as needed. However, this technique suffers most of the disadvantages, discussed above, of the linked list approach. When a particular operation involves memory on more than one page, the page number in the page register must be changed at each jump between pages. Both of these techniques are inefficient in a virtual storage environment, because they tend to be scattered throughout memory, thereby requiring a large amount of swapping into and out of virtual memory. Also, both techniques are not suitable for taking advantage of numerous techniques for dealing with contiguous blocks of storage such as indexing, block moves, and searching. Therefore, a technique is needed which enables dynamic structures to grow or shrink without the need for time consuming block moves and which preserves the ability to store each structure in a contiguous block of addresses.